// 广度优先搜索
// 使用队列存放每一层的节点，然后在循环中记录值，并且把子节点添加进去
// 外循环负责遍历层级结构，内循环负责遍历每一层的子节点
var levelOrder = function (root) {
  if (!root) return [];
  let res = [],
    queue = [root];
  while (queue.length) {
    // 当前层的节点数
    let len = queue.length;
    // 当前层的节点值数组
    let curLevel = [];
    while (len--) {
      let cur = queue.shift();
      curLevel.push(cur.val);
      if (cur.left) queue.push(cur.left);
      if (cur.right) queue.push(cur.right);
    }
    res.push(curLevel);
  }
  return res;
};
